package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author shiminghui
 * @date 2025/3/16 17:19
 * @description: TODO
 */
public class _056_完全背包问题 {

    @Test
    public void test1() {

        Item[] items = new Item[]{new Item(1, 2, 3),
                new Item(2, 4, 7),
                new Item(3, 3, 4)};
        System.out.println(completePack2(items, 6));
    }

    private int completePack(Item[] items, int maxWeight) {
        int dp[][] = new int[items.length][maxWeight + 1];
        for (int i = 0; i < items.length; i++) {
            for (int j = 0; j < maxWeight + 1; j++) {
                if (i == 0) {
                    if (items[i].weight <= j) {
                        dp[i][j] = items[i].value + dp[i][j - items[i].weight];
                    }
                } else {
                    if (items[i].weight <= j) {
                        dp[i][j] = Math.max(dp[i - 1][j], items[i].value + dp[i][j - items[i].weight]);
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[items.length - 1][maxWeight];
    }

    /**
     * 降维
     */
    private int completePack2(Item[] items, int maxWeight) {
        int dp[] = new int[maxWeight + 1];
        for (int i = 0; i < items.length; i++) {
            for (int j = 0; j <= maxWeight; j++) {
                if (j >= items[i].weight) {
                    dp[j] = Math.max(dp[j], items[i].value + dp[j - items[i].weight]);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[maxWeight];
    }


    private static class Item {
        int id;
        int weight;
        int value;

        public Item(int id, int weight, int value) {
            this.id = id;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Item{" +
                    "id=" + id +
                    ", weight=" + weight +
                    ", value=" + value +
                    '}';
        }
    }
}
